package leetcode.code1601;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution3 implements IDebug {

	int ans;
	int[][] requests;
	int len;

	public int maximumRequests(int n, int[][] requests) {
		int[] buildings = new int[n];
		this.ans = 0;
		this.len = requests.length;
		this.requests = requests;
		this.find(buildings, 0, 0);
		return ans;
	}

	private void find(int[] buildings, int index, int achievable) {
		if (index == len) {
			boolean ok = true;
			for (int num : buildings) {
				if (num != 0) {
					ok = false;
					break;
				}
			}
			if (ok) {
				this.ans = Math.max(this.ans, achievable);
			}
			return;
		}
		int[] request = this.requests[index];
		int sub = request[0];
		int add = request[1];
		buildings[sub]--;
		buildings[add]++;
		this.find(buildings, index + 1, achievable + 1);
		buildings[sub]++;
		buildings[add]--;
		if (sub != add) {
			this.find(buildings, index + 1, achievable);
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare(5, this.maximumRequests(5, HelpDebug.str2array1("[[3,4],[1,0],[0,1],[0,1],[1,2],[2,0]]")));
	}

	@Override
	public void debug2() {
		HelpDebug.compare(3, this.maximumRequests(3, HelpDebug.str2array1("[[0,0],[1,2],[2,1]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
//		20
//		[[0,3],[0,0],[0,1],[1,2],[2,1],[3,4],[7,9],[15,14],[13,14],[16,11],[9,10],[9,11],[11,7]]
	}

	@Override
	public void debug4() {
		HelpDebug.compare(6, this.maximumRequests(20, HelpDebug.str2array1(
				"[[0,3],[0,0],[0,1],[1,2],[2,1],[3,4],[7,9],[15,14],[13,14],[16,11],[9,10],[9,11],[11,7]]")));
	}

	public void debug5() {
		HelpDebug.compare(7, this.maximumRequests(3, HelpDebug.str2array1("[[1,2],[0,0],[0,2],[0,1],[0,0],[0,2],[1,0],[0,1],[2,0]]")));
//		[,,[0,2],,,[0,2],[1,0],[0,1],]
//				[0,1] [1,2] [2,0]
//						[0,0] [0,0]
	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug5();
		so.debug2();
		so.debug1();
		so.debug3();
		so.debug4();
	}

}
